Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 4
з дисципліни «Програмування складних алгоритмів»
Тема «Методи пошуку у масивах»
Варіант № 11
Лабораторна робота № 4:
Методи пошуку у масивах
Мета: отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами, дослідження і вивчення методів пошуку ключових елементів у масивах, здійснення порівняння та аналізу ефективності використовуваних методів пошуку.
Завдання до лабораторної роботи
Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром.
Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом.
№ варіанту
Метод пошуку
11
Бінарний пошук
Теоретичні відомості
Алгоритм пошуку — алгоритм, який вирішує задачу пошуку, тобто, знаходить інформацію, яка зберігається в певній структурі даних. Структури даних можуть бути реалізовані за допомогою зв'язаних списків, масивів, дерев пошуку, хеш-таблиць чи інших методів зберігання інформації. Алгоритм пошуку на пряму залежить від структури даних, для якої він реалізований.
Алгоритми пошуку класифікуються на основі їх механізму пошуку. Є послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних, лінійний та бінарний пошуки, алгоритм Рабіна-Карпа, метод пошуку з бар’єром та ін.
Лінійний пошук
Лінійний пошук належить до найбільш простих способів пошуку даних. Мета лінійного пошуку – знайти потрібний елемент (ключ) в масиві даних. В алгоритмі лінійного пошуку кожен елемент масиву послідовно порівнюється з ключем до тих пір, поки не буде знайдено потрібний елемента або не буде проскановано увесь масив.
В контексті лінійного пошуку можуть виникати наступні задачі:
визначити наявність заданого елементу в масиві (наборі даних);
визначити кількість входжень заданого елементу в масиві;
визначити номер позиції або масив номерів позицій розміщення заданого елементу в масиві.
Реалізація лінійного пошуку може бути розширена для використання в багатовимірних масивах.
Приклад:
int find(int *arr, int size, int key) {
int last = arr[size - 1];
arr[size - 1] = key
int i = 0;
for (i = 0; arr[i] != value; ++i) {
arr[size - 1] = last;
if (i != (size - 1) || value == last) {
return i;
}
еlse
{
return -1;
}
}
}
Пошук бар’єром
Ідея пошуку з бар'єром полягає в тому, щоб не перевіряти щораз у циклі умови, пов'язаної із границями масиву. Це можна забезпечити, установивши в масив так званий бар'єр: будь-який елемент, що задовольняє умові пошуку. Тим самим буде обмежена зміна індексу.
Вихід із циклу, у якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар'єрі. Таким чином, після виходу із циклу перевіряється, чи не бар'єр ми знайшли? Обчислювальна складність пошуку з бар'єром менша, ніж у лінійного пошуку, але також є величиною того ж порядку, що й N - кількість елементів масиву.
Існує два способи установки бар'єра: додатковим елементом або замість крайнього елемента масиву.
Приклад:
int LіnSearchQuіck(іnt m[n+1], іnt key)
{
іnt і=0;
M[n]=key;
whіle (m[і]!=key) і++ ;
іf (і==n+1)
return – 1;
else
return і;
}
Двійковий (Бінарний) пошук
Алгоритм двійкового пошуку можна використати для пошуку елемента із заданою властивістю тільки в масивах, упорядкованих по цій властивості. Так при пошуку числа із заданим значенням необхідно мати масив, упорядкований по зростанню або по убуванню значень елементів. А, наприклад, при пошуку числа із заданою сумою цифр масив повинен бути впорядкований по зростанню або по убуванню сум цифр елементів.
Ідея алгоритму полягає в тому, що масив щораз ділиться навпіл і вибирається та частина, де може перебувати потрібний елемент. Розподіл триває поки частина масиву для пошуку більше одного елемента, після чого залишається перевірити цей елеме...
